/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-11-27
 * Time: 23:27
 */
public class test2 {
    /*
    LeetCode 75  颜色分类
    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

    我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     */

    // 分治：将一个大问题转化为若干个相同类型的子问题
    // 快排
    //0 -> swap(nums[++left],nums[i++])
    //1 -> i++;
    //2 -> swap(nums[--right],nums[i])      i千万不能++


    public void sortColors(int[] nums) {
        int left = -1;
        int right = nums.length;
        int i = 0;
        while(i<right){
            if(nums[i]==0){
                swap(nums,++left,i++);
            }else if(nums[i]==1){
                i++;
            }else{
                swap(nums,--right,i);
            }
        }
    }

    public void swap(int []nums,int right,int left){
        int tmp = nums[right];
        nums[right] = nums[left] ;
        nums[left] = tmp;
    }
}
